package top.humbleyuan.dp;

/**
 * @Author HumbleYuan
 * @Date 2020/5/18 21:25
 * @Des 不同的二叉搜索树
 */
public class LeetCode_96 {
    /**
     * 不同的二叉搜索树
     *  G(n)表示n个数字一共有的个数
     *  F(i,n)表示以i为根的情况下一共有的个数
     *  由G(n) = 左 * 右(i<=n)，且有二叉搜索树的特性
     *  即F(i,n) = G(i-1) * G(n-i);
     *  G(n) = F(1,n) + F(2,n) + ... + F(n,n)
     *
     *  G(0) = 1,G(1) = 1,G(2) = 2
     *  G(3) = F(1,n) + F(2,n) + F(3,n) = G(0)*G(2) + G(1)*G(1) + G(2)*G(0)
     *  ...
     */
    public static void main(String[] args) {
        int n = 3;
        if(n <= 1) {
            System.out.println("有1种");
            return;
        }

        if(n == 2) {
            System.out.println("有2种");
            return;
        }

        int[] count = new int[n+1];

        // 初始状态
        count[0] = count[1] = 1;
        count[2] = 2;


        for (int i = 3;i <= n;i++) {
            int tempCount = 0;

            for (int j = 1;j <= i;j++) {
                tempCount += count[j-1] * count[i-j];
            }
            count[i] = tempCount;
        }

        System.out.println("共有" + count[n] + "种二叉树");
    }
}
